//K次取反后最大化的数组和   力扣1005
//贪心 
// 法一：
// 要先优先反转绝对值大的负数，将数组按从小到大排序，
// 那么负数就会按绝对值从大到小的顺序排列，从左向右遇到负数就反转
// 若遍历结束后，k==0,说明负数刚好被反转完或还有剩余的绝对值相对最小的负数，这时为最优解
// 若遍历结束后，k != 0,说明负数全部被反转，那么剩余的次数就要用来反转值最小的数，此时为最优解
// 那么就再从小到大排序，然后剩余次数都用来反转第一个元素，最后求和
// 法二：
// 直接将数组按绝对值从大到小排序，再从左到右依次反转，
// 若k==0则直接求和
// 若k ！= 0,则都用来反转最后一个元素即可

//法一
class Solution {
public:
	int largestSumAfterKNegations(vector<int>& nums, int k) {
		sort(nums.begin(),nums.end());
		for(int i = 0; i < nums.size() && k > 0; i++)
		{
			if(nums[i] < 0) 
			{
				nums[i] = -nums[i];
				k--;
			}
		}
		int sum = 0;
		if(k == 0)
			for(int j = 0; j < nums.size(); j++) sum += nums[j];
		else
		{
			sort(nums.begin(),nums.end());
			if(k%2 != 0)
				nums[0] = -nums[0];
			for(int j = 0;j < nums.size();j++) sum += nums[j];
		}    
		return sum;
	}
};
//法二
class Solution {
public:
	static bool cmp(int a,int b)
	{
		return abs(a) > abs(b);
	}
	int largestSumAfterKNegations(vector<int>& nums, int k) {
		sort(nums.begin(),nums.end(),cmp);
		for(int i = 0; i < nums.size() && k > 0; i++)
		{
			if(nums[i] < 0) 
			{
				nums[i] = -nums[i];
				k--;
			}
		}
		int sum = 0;
		if(k%2 != 0)
			nums[nums.size()-1] *= -1;
		for(int j = 0;j < nums.size();j++) sum += nums[j];
		return sum;
	}
};
